<?php
/**
 * @title 31. 下一个排列 - 倒序
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[] $nums
     * @return NULL
     */
    function nextPermutation(&$nums) {
        if(count($nums) <= 1){
            return $nums;
        } else {}

        /**
         * @since 2020-07-04 倒序找到非降序的值
         *
         * ..., 2, 4,3,1
         *      ↑
         *      i
         */
        $len = count($nums);
        for($i=$len-2; $i>=0; $i--){
            if($nums[$i+1] > $nums[$i]){
                break;
            } else {}
        }

        /**
         * @since 2020-07-04 完全降序, 改升序
         */
        if($i<0){
            $nums = self::revArray($nums, 0, $len-1);
            // $nums = array_reverse($nums);
        } else {
            /**
             * @since 2020-07-04 倒序找到第一个比nums[i]大的元素, 和它交换
             * ..., 2, 4,3,1
             *      ↑    ↑
             *      i    j
             */
            for ($j=$len-1; $j>=0; $j--){
                if($nums[$j] > $nums[$i]){
                    list($nums[$i], $nums[$j]) = [$nums[$j], $nums[$i]];
                    break;
                } else {}
            }

            /**
             * @since 2020-07-04 i+1到len-1, 改升序
             * ..., 3, 4,2,1
             *         ↑   ↑
             *       i+1   len-1
             */
            $nums = self::revArray($nums, $i+1, $len-1);
        }

        /**
         * @return
         */
        return $nums;
    }

    /**
     * @title 反转数组某段
     * @author start2004
     * @since 2020-07-03 Created
     *
     * @param array $nums
     * @param int $left
     * @param int $right
     * @return array
     */
    function revArray($nums = [], $left = 0, $right = 0){
        while($left<$right){
            list($nums[$left], $nums[$right]) = [$nums[$right], $nums[$left]];
            $left++;
            $right--;
        }

        /**
         * @return
         */
        return $nums;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.03_5.php
 */
$datas = [
    [1,2,3],
    [3,2,1],
    [1,1,5],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
